#include<iostream>
#include<vector>
#include<unordered_map>
using namespace std;

class Node {
public:
	int val;
	Node* next;
	Node* random;

	Node(int _val) {
		val = _val;
		next = NULL;
		random = NULL;
	}
};

class Solution {
public:
	Node* copyRandomList(Node* head) {
		if (!head) return NULL;
		unordered_map<Node *, int> map;
		vector<Node *>list;
		int index = 0;
		Node *mylist=new Node(-1),*tail=mylist,*iter=head;
		while (iter) {
			map[iter] = index++;
			Node *node = new Node(iter->val);
			list.push_back(node);
			tail->next = node;
			iter = iter->next;
			tail = tail->next;
		}
		Node *temp = head,*current=mylist->next;
		index = 0;
		while (temp) {
			if (temp->random) {
				int index = map[temp->random];
				current->random = list[index];
			}
			temp = temp->next;
			current = current->next;
		}
		return mylist->next;
	}
};

void main() {
	Node root(7), n13(13), n11(11), n10(10), n1(1);
	root.next = &n13;
	n13.next = &n11;
	n11.next = &n10;
	n10.next = &n1;
	root.random = &n1;
	n13.random = &root;
	n11.random = &n1;
	n10.random = &n11;
	n1.random = &root;
	Solution s;
	s.copyRandomList(&root);
}